We define and study the Functional Aggregate Query (FAQ) problem, whichcaptures common computational tasks across a very wide range of domainsincluding relational databases, logic, matrix and tensor computation,probabilistic graphical models, constraint satisfaction, and signal processing.Simply put, an FAQ is a declarative way of defining a new function from adatabase of input functions. We present "InsideOut", a dynamic programming algorithm, to evaluate an FAQ.The algorithm rewrites the input query into a set of easier-to-compute FAQsub-queries. Each sub-query is then evaluated using a worst-case optimalrelational join algorithm. The topic of designing algorithms to optimallyevaluate the classic multiway join problem has seen exciting developments inthe past few years. Our framework tightly connects these new ideas in databasetheory with a vast number of application areas in a coherent manner, showingpotentially that a good database engine can be a general-purpose constraintsolver, relational data store, graphical model inference engine, andmatrix/tensor computation processor all at once. The InsideOut algorithm is very simple, as shall be described in this paper.Yet, in spite of solving an extremely general problem, its runtime either is asgood as or improves upon the best known algorithm for the applications that FAQspecializes to. These corollaries include computational tasks in graphicalmodel inference, matrix/tensor operations, relational joins, and logic. Betteryet, InsideOut can be used within any database engine, because it is basicallya principled way of rewriting queries. Indeed, it is already part of theLogicBlox database engine, helping efficiently answer traditional databasequeries, graphical model inference queries, and train a large class of machinelearning models inside the database itself.
展开▼
